This invention relates generally to wireless cellular networks, and, more particularly, to methods for finding the current cell of a wireless cellular network in which a user resides.
In a cellular network, when a call to the mobile user arrives, a mobility management scheme is responsible for finding the current cell in which a mobile user resides. Typically, a mobility management scheme constitutes of a location update scheme and a paging scheme.
Over the last several years, the worldwide cellular communications market has experienced explosive growth. This growth has been driven by the decrease in prices of cellular service and phones and improved service. In general, as the number of subscribers increases for a fixed radio spectrum allocation, the size of wireless coverage cells must decrease, in order to accommodate the higher subscriber densities. As cells decrease in size, the problem of efficient location management becomes more difficult due to the additional signaling created by more subscribers and more cells. The additional signaling uses electromagnetic spectrum bandwidth, a scarce resource.
In the last decade, many location update schemes were proposed. Basically, these schemes were either movement-based, timer-based, distance-based, profile-based, state-based, or velocity-based. Schemes that use a hybrid of the above strategies were also proposed. It has been proven that distance-based schemes achieve better performance compared to movement-based schemes and timer-based schemes. Some proposed schemes suggested that a mobile user should register its location only when it enters some predefined cells, referred to as reporting centers. An information theoretic approach for location update and derivation of probabilistic information about locations of mobile users has been proposed (Amiya Bhattacharya and Sajal K. Das, “LeZi-Update: An Information-Theoretic Approach to Track Mobile Users in PCS Networks”, MOBICOM 1999. Pages 1–12).
A location area is composed of a number of cells. Some researchers assumed that a mobile user sends a location update message to the system whenever it enters a new location area and concentrated on the design of an optimal location area. Kim and Lee proposed an integer-programming model to find the optimal location area, which may take on an irregular shape. Other researchers assumed that location areas are given and focused on the decision problem of whether a mobile user should send a location update message when it enters a new location area.
Recently, a convex optimization problem was formulated to minimize the costs of location update and paging in the movement-based location update scheme (Jie Li, Hisao Kameda, and Keqin Li, “Optimal dynamic mobility management for PCS networks”, IEEE/ACM Transactions on Networking, vol. 8, no. 3 p. 319–27, June 2000.). A continuous formulation of the problem of one-dimensional location area design has been proposed to overcome the computational difficulty associated with the original combinatorial formulation. An improved probabilistic location update scheme has been proposed. Probabilistic paging has also been used for contention-free mobility management (Wing Ho A. Yuen and Wing Shing Wong, “A contention-free mobility management scheme based on probabilistic paging”, IEEE Transactions on Vehicular Technology, vol. 50, no. 1, p. 48–58, January 2001).
There is an intrinsic tradeoff between location update and paging. As the frequency of location update increases, the location uncertainty decreases and therefore the paging cost decreases. And on the contrary, when the frequency of location update decreases, both the location uncertainty and paging cost increase. It is possible to see paging as a more fundamental operation than location update. However, as it has been pointed out, “the majority of the research on location management has actually focused on update schemes, assuming some obvious version of the paging algorithm.”
The concept of dividing a location area into paging zones has been previously described. Lyberopoulos (G. L. Lyberopoulos, J. G. Markoulidakis, D. V. Polymeros, D. F. Tsirkas and E. D. Sykas, “Intelligent paging strategies for third generation mobile telecommunication systems”, IEEE Transactions on Vehicular Technology, vol. 44, no. 3, p. 543–553, August 1995) proposed to page the cell that a mobile user registered with most recently and then page all other cells in the location area if necessary. Rose and Yates (C. Rose and R. Yates, “Minimizing the average cost of paging and registration: A timer-based method”, Wireless Networks, 2(2):109–116, June 1996) proved that given the probabilistic information about the position of a mobile user, to minimize the average paging cost, the cells with the higher probabilities must be paged before the cells with the lower probabilities are paged. Krishnamachari, Gau, Wicker, and Haas (Bhaskar Krishnamachari, Rung-Hung Gau, Stephen B. Wicker, Zygmunt J. Haas, “Optimal Sequential Paging in Cellular Networks”, IEEE Vehicular Technology Conference, Fall 2001) proposed an efficient algorithm to solve the problem of minimizing the average paging cost under the worst-case paging delay constraint.
All the above works on paging focused on the problem of searching for a single mobile user and assumed that some straightforward strategy of searching for multiple mobile users, such as sequential search, is used.
Rose et al.(C. Rose and R. Yates, “Minimizing the average cost of paging and registration: A timer-based method”, Wireless Networks, 2(2):109–116, June 1996) proposed a sequential paging scheme to locate a single mobile user in the cellular network based on the probabilistic information of the location of the mobile user. The basic idea of such a system resides in partitioning cells in the network into a number of paging zones and search for paging zones one by one. More precisely, the system pages the first paging zone in the first time slot. If the mobile user is in the first paging zone, the mobile user is located and the search is aborted. Otherwise, the system pages the second paging zone, and so on.
In U.S. Pat. No. 6,181,945 (Jan. 30, 2001), Lee discloses a method for paging a single user based on minimizing the paging cost.
All the above described work focuses on the problem of searching for a single mobile user. However, it is more efficient for a multi-user system to service many paging requests simultaneously (or concurrently). A model has been proposed for the concurrent paging problem but it makes assumptions about the arrival times and/or the resident times of mobile users (D. Goodman, P. Krishnan, B. Sugla, “Minimizing queuing delays and number of messages in mobile phone location”, Mobile Networks and Applications, Vol. 1, p. 39–48, 1996; C. Rose and R. Yates, “Ensemble polling strategies for increased paging capacity in mobile communications networks”, ACM Wireless Networks, Vol. 3, No. 2, p. 159–167, 1997, see also http://citeseer.nj.nec.com/rose96ensemble.html).
Consequently, a less restrictive and more efficient concurrent paging scheme is needed. A concurrent paging scheme that minimizes the expected number of the required paging messages would be highly desirable.
It is therefore an object of this invention to provide a concurrent paging scheme that minimizes the expected number of the required paging messages.
It is a further object of this invention to provide concurrent paging schemes that can be easily computed and provide a reduction of the expected number of the required paging messages.